//给你一个 n x n 矩阵 matrix ，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。
//请注意，它是 排序后 的第 k 小元素，而不是第 k 个 不同 的元素。
//
//
//
// 示例 1：
//
//
//输入：matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8
//输出：13
//解释：矩阵中的元素为 [1,5,9,10,11,12,13,13,15]，第 8 小元素是 13
//
//
// 示例 2：
//
//
//输入：matrix = [[-5]], k = 1
//输出：-5
//
//
//
//
// 提示：
//
//
// n == matrix.length
// n == matrix[i].length
// 1 <= n <= 300
// -109 <= matrix[i][j] <= 109
// 题目数据 保证 matrix 中的所有行和列都按 非递减顺序 排列
// 1 <= k <= n2
//
// Related Topics 堆 二分查找
// 👍 608 👎 0

/**
 * @author DaHuangXiao
 */
package leetcode.editor.cn;

public class KthSmallestElementInASortedMatrix {
    public static void main(String[] args) {
        Solution solution = new KthSmallestElementInASortedMatrix().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        // 第k小的问题,用值二分+计数判断解决
        // 如果是数组一般用下标二分+目标值判断解决
        public int kthSmallest(int[][] matrix, int k) {
            int left = matrix[0][0];
            int right = matrix[matrix.length-1][matrix[0].length-1];

            while (left<=right){
                int mid = left+(right-left)/2;
                if (findCount(mid,matrix)>=k){
                    right = mid-1;
                }else {
                    left = mid+1;
                }
            }
            return left;
        }

        private int findCount(int mid, int[][] matrix) {
            int count =0;
            int j =0;
            for (int i = 0; i < matrix.length; i++) {
                for (j=0; j < matrix[0].length; j++) {
                    if (matrix[i][j]<=mid){
                        count++;
                    }else {
                        break;
                    }
                }

            }
            return count;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}